1. Field of the Invention
The present invention relates generally to computing systems involving a queue for accommodating multiple user requests, and particularly, to a novel method for handling process requests in a manner that prevents starvation of a user's request.
2. Discussion of the Prior Art
Priority queuing schemes are used in computing environments where certain requests are deemed to be of more importance than other requests.
For example, a particular environment may be established such that priorities are assigned to requests based on whether the requester is waiting for the request to complete before continuing processing (synchronous), or if the requestor will not wait for the request to complete before processing other work (asynchronous). Synchronous requests may be assigned a priority 100 and “no wait” requests are assigned a priority 50. Thus, when a request is submitted, it is placed on the work queue based on the priority of the request. Synchronous requests are placed at the head of the queue to be selected first, and asynchronous requests are placed at the tail of the queue to be processed only after all synchronous requests have been processed.
In such systems that implement a queue to process work requests, queue entries are generally placed on the queue in FIFO order or according to some designated priority. When a work request is being selected, the processor simply removes an entry from the Head/Tail of the queue. If a single user submits a large number of requests, and then a second user (of equal importance or priority) submits subsequent requests, then the second user's request undergoes processor starvation since it is unable to have any of its requests processed until all of the requests of the first user are completed. In this scenario, the FIFO queue creates a situation of unfairness by allowing a single user to dominate request processing and not allowing other requests from other users to be processed, even though all of the requests have equal priority.
While algorithms exist today that implement round robin using different physical queues, link lists, etc., none of these systems present a system for interleaving requests based on keys in a constrained environment. For example, IBM's Data Facility Storage Management Subsystem: Hierachical Storage Manager (DFSMShsm) (an element of the DFSMS/MVS software storage solution for the OS/390 and z/OS IBM mainframe operating systems), is a disk storage management and productivity tool for managing low-activity and inactive data. It provides backup, recovery, migration, and space management functions as well as full function disaster recovery. DFSMShsm improves disk use by automatically managing both space and data availability in a storage hierarchy by implementing a link list and organizing requests on that queue. Thus, when placing a new request, the system begins at the head of the queue and traverses the queue until an appropriate location for the new request is found based on the priority and the requestor. For example, if one person submits a new synchronous request, then the queue would have to be traversed until that person's last existing synchronous request, or until a person is found with the next lower priority. The worst case scenario is that the entire length of the queue must be traversed before finding the placement location for the new request.
Thus, it would be highly desirable to provide some fairness to the queuing system so that a single user can not dominate the processor while other users have to wait for the first user's requests to be complete.
It would be further highly desirable to provide a system and methodology for sorting such requests based on the submitter such that requests from different users are interleaved so that no one user has all of their requests selected for processing while other users' requests have to wait.